#pragma once  //为了避免同一个头文件被包含（include）多次

#include<queue>
#include<vector>
#include<functional>

using namespace std;

template<class W>  //类模板的定义   W代表权值
struct HuffmanTreeNode   //二叉树节点的定义
{
    HuffmanTreeNode<W>* left;
    HuffmanTreeNode<W>* right; 
    HuffmanTreeNode<W>* parent;
    W weight;

    HuffmanTreeNode(const W& w = W())   //构造函数
        :  left(nullptr)    //构造函数初始化列表以一个冒号开始, 
           , right(nullptr)   //接着是一个逗号分割的数据成员列表,
           , parent(nullptr)  //每一个数据成员后面跟一个放在圆括号中的初始化式.
           , weight(w)        
    {}

};

template <class W>
struct Compare
{
    typedef HuffmanTreeNode<W> Node;
    bool operator()(const Node* left, const Node* right)
    {
        return left->weight > right->weight; 

    }

};

template<class W>   

class HuffmanTree
{
    typedef HuffmanTreeNode<W> Node;  //取别名
    public:
    HuffmanTree()
        :root(nullptr)
    {}
    ~HuffmanTree()
    {
        Destroy(root);

    }
    void CreateHuffmanTree(const W array[], size_t size,const W& invalid) // 创建Huffman二叉树.权值以数组的形式给进去
    {
        //小堆---优先级队列默认情况下是大堆，只需要修改其比较规则
        std::priority_queue<Node*,vector<Node*>,Compare<W>> q; 

        //1.先使用所给的权值创建只有根节点的二叉树森林
        for (size_t i = 0; i < size; ++i)  //对数组进行遍历
        {
            if (array[i]!=invalid)  //如果不等于无效的数，无效的数就是0
                q.push(new Node(array[i]));  //将节点放入到优先级队列中 
        }

        //2.循环进行以下步骤，直到二叉树森林中只剩下一颗二叉树位置
        while (q.size()>1)
        { 
            //从二叉树森林中先取权值最小的两棵二叉树
            Node* left = q.top();  //小堆是已经排列好了的，只需取顶部元素就是最小的
            q.pop();
            Node* right = q.top();
            q.pop();
            //将left和right作为某个新节点的左右子树，构造一个新的二叉树
            //新二叉树根节点的权值就是左右孩子权值之和
            Node* parent = new Node(left->weight + right->weight);
            parent->left = left;
            parent->right = right;
            left->parent = parent;
            right->parent = parent; 
            //将新的二叉树插入到二叉树森林中
            q.push(parent);
        }
        root = q.top();  //最后一个节点就是根节点
    }

    Node* GetRoot()
    {
        return root;
    }

    void Destroy(Node*& proot)
    {
        if (proot)
        {
            Destroy(proot->left);
            Destroy(proot->right);
            delete proot;
            proot = nullptr;
        }
    }
    private:
    Node* root;

};

//void TestHuffmanTree()
//{
//  int array[] = { 3, 1, 5, 7  };
//  HuffmanTree<int> t;  //权值是int类型的
//  t.CreateHuffmanTree(array, sizeof(array) / sizeof(array[0]));
//}
